package cn.bellychang.leetcode.question207;

import java.util.*;

/**
 * @author ChangLiang
 * @date 2021/3/18
 */
public class Solution {

    /**
     * 图中有无环的存在 使用BFS拓扑排序
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {


        // 初始化图 使用邻接表的方式
        Map<Integer, List<Integer>> adj = new HashMap<>(numCourses);

        // 存储每个结点的入度
        int[] indegree = new int[numCourses];

        // 构建图
        for (int i = 0; i < prerequisites.length; i++) {
            int first = prerequisites[i][0];
            int second = prerequisites[i][1];
            if (!adj.containsKey(first)) {
                adj.put(first, new ArrayList<>());
            }
            adj.get(first).add(second);
            // 入度加一，从first->second
            indegree[second]++;
        }


        // 存储所有入度为0的结点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 用来计算拓扑排序的结点个数
        int count = 0;
        while (!queue.isEmpty()) {

            // 获取第一格入度为0的结点
            int val = queue.poll();
            count++;

            // 判断很关键 如果不包含 说明其没有依赖于其他course的情况
            if (!adj.containsKey(val)) {
                continue;
            }

            // 获取val的临结点
            List<Integer> temp = adj.get(val);

            for (int i = 0; i < temp.size(); i++) {

                // 把所有的以val为开头的入度减一
                int idx = temp.get(i);
                indegree[idx]--;

                // 如果入度为0，则把该结点加入队列中
                if (indegree[idx] == 0) {
                    queue.offer(idx);
                }
            }
        }

        // 如果最后输出出来的顶点个数，少于图中顶点个数，图中还有入度不是 0 的顶点，那就说明，图中存在环
        return count == numCourses;
    }
}
